package org.xingole.daily;

import java.util.Arrays;

/**
 * <a href="https://leetcode.com/problems/maximize-the-minimum-powered-city">
 * Problem Description
 * </a>
 * 
 * @since 2025-11-7
 */
public class MaximizeTheMinimumPoweredCity {
    /**
     * 
     * @param stations an integer array where stations[i] represents the number of
     * power stations in the ith city.
     * @param r the range the power station can cover.
     * @param k the more power stations that the government has sanctioned building.
     * @return the maximum possible minimum power of a city, if the additional power
     * stations are built optimally.
     */
    public long maxPower(int[] stations, int r, int k) {
        int n = stations.length;

        // We use a difference array to efficiently calculate the total power for each
        // city.
        long[] cnt = new long[n + 1];
        for (int i = 0; i < n; i++) {
            int left  = Math.max(0, i - r);
            int right = Math.min(n, i + r + 1);
            cnt[left]  += stations[i];
            cnt[right] -= stations[i];
        }

        // Lower bound: minimum power among all cities without adding any new stations.
        long lo = Arrays.stream(stations).min().getAsInt();
        // Upper bound: total power of all existing stations plus all k new stations
        long hi = Arrays.stream(stations).asLongStream().sum() + k;

        long res = 0;
        // Use binary search to determine the highest possible minimum power supply across
        // all cities. The key is to verify whether a given power level x can satisfy the 
        // problem’s requirement; that is, whether it is possible for every city’s power supply 
        // to be at least x after adding k additional power stations.
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (check(cnt, mid, r, k)) {
                res = mid;
                lo  = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return res;
    }

    private boolean check(long[] cnt, long val, int r, int k) {
        // Suppose the target minimum power for each city is val. We traverse the cities from
        // left to right.
        int n = cnt.length - 1;
        long[] diff = cnt.clone();
        long sum = 0;
        long remaining = k;

        for (int i = 0; i < n; i++) {
            sum += diff[i];
            // sum is the power at index i without the additional stations.
            if (sum < val) {
                long add = val - sum;
                if (remaining < add) {
                    return false;
                }
                // The optimal choice is to add a power station at i+r.
                // Since we are traversing in order, by the time we reach city i, 
                // all cities before it already have sufficient power
                remaining -= add;
                int end = Math.min(n, i + 2 * r + 1);
                diff[end] -= add;
                sum += add;
            }
        }
        return true;
    }
}
